An integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, and wires that are fabricated by forming layers of different materials and of different geometric shapes on various regions of a silicon wafer.
Many phases of physical design may be performed with computer aided design (CAD) tools or electronic design automation (EDA) systems. To design an integrated circuit, a designer first creates high level behavior descriptions of the IC device using a high-level hardware design language. An EDA system typically receives the high level behavior descriptions of the IC device and translates this high-level design language into netlists of various levels of abstraction using a computer synthesis process. A netlist describes interconnections of nodes and components on the chip and includes information of circuit primitives, such as for example, transistors and diodes, their sizes and interconnections. An integrated circuit designer may use a set of layout EDA application programs to create a physical design of the IC from the logical design. The layout EDA application uses geometric shapes of different materials to create the various electrical components on an integrated circuit and to represent electronic and circuit IC components as geometric objects with varying shapes and sizes. The geometric information about the placement of the nodes and components onto the chip may be determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip. The routing process is a process for creating interconnections between the blocks and components according to the specified netlist. After an integrated circuit designer has created an initial integrated circuit layout, the designer then verifies and optimizes the integrated circuit layout using a set of EDA testing and analysis tools. Verification may include, for example, design rule checking to verify compliance with rules established for various IC parameters.
Generally, the routing process is computationally intensive. A typical IC design may contain thousands of geometric objects representing electronic and circuit IC components that need to be interconnected while satisfying numerous constraints. For example, an object from one class may require a certain spacing from its nearest neighbor object so that the two do not interfere with each other. Further, object spacing rules arise due to the limitations inherent in the semiconductor manufacturing process. For example, when creating IC objects using a lithography manufacturing processes, objects can only be so small, so thin, or so close to one another before the physics of the substrate, mask, and incoming irradiating light start producing errors in design. Further complications arise due to the fact that some objects cannot share wires or buses with other objects and instead require dedicated routes to their destination. Finally, in many designs, it is preferable to optimize the routed designs so that individual objects are connected using the shortest route possible. This is in part due to the fact that wires routed along long paths tend to cause noise, power dissipation, and timing issues. The above factors compound to create a very complex problem for route tools to solve.
Conventional route tools approach this problem by modeling each geometric object as a crude data set. Every object has corresponding data, and the route tool must track many thousands of objects, each with their own constraints and parameters, in an effort to optimize routes. However, this approach is not only computationally intensive, it often yields inefficient overly complex designs that are produced at higher costs.